#include <stdio.h>
#define N 8
void make_A_heap(int a[], int end)
{
    int pa = 0;
    int tag = 1;
    int t;
    while (1)   //大循环保证最后成为堆
    {
        pa = end / 2;
        tag = 0;
        while (pa)   //跑完其中一圈
        {
            if (a[pa] < a[2 * pa])  //双亲比左子女小
            {
                t = a[pa];
                a[pa] = a[2 * pa];
                a[2 * pa] = t;
                tag = 1;    //置标志位
            }
            if ((2 * pa + 1) <= end && a[pa] < a[2 * pa + 1])  //双亲比右子女小
            {
                t = a[pa];
                a[pa] = a[2 * pa + 1];
                a[2 * pa + 1] = t;
                tag = 1;    //置标志位
            }
            pa--;
        }
        if (!tag)
            break;
    }
}

//堆排序
void HeapSort(int a[])
{
    int end, t;
    end = N;
    while (end > 1)
    {
        //调整大根堆
        make_A_heap(a, end);
        t = a[1];
        a[1] = a[end];
        a[end] = t;
        end--;
    }
}
int main()
{
    int i;
    int Data[N + 1] = { 0, 3, 2, 5, 8, 4, 7, 6, 9 };
    HeapSort(Data);
    for (i = 1; i < N + 1; i++)
        printf("%5d", Data[i]);
    printf("\n");
    return 0;
}